package leetcode_141_160;

import java.util.HashMap;

/**
 * 满足  LRU (最近最少使用) 缓存 约束的数据结构。
 */
public class LRUCache {
    /*
     * 基本思路是使用hash表进行快速定位
     * 将新加入或者刚处理过的数据提到最前面
     * 需要使用双向链表存储数据，便于节点的直接移动
     * 让hash表和双向链表进行映射
     * 53ms
     */

    public class node{
        public int key,val;

        public node pre,next;

        node(int Key,int Val){
            val=Val;
            key=Key;
        }
    }

    public class doubleList{
        int size;
        //初始化头尾节点
        node head=new node(0,0);
        node tail=new node(0,0);

        //初始化
        doubleList(){
            head.next=tail;
            tail.pre=head;
            size=0;
        }

        void addFirst(node node){
            node.next=head.next;
            head.next.pre=node;
            head.next=node;
            node.pre=head;
            size++;
        }

        /**
         * 删除对应节点
         */
        void remove(node n){
            n.pre.next = n.next;
            n.next.pre = n.pre;
            size--;
        }

        /**
         * 删除并返回末尾节点
         */
        private node removeLast() {
            node last = tail.pre;
            remove(last);
            return last;
        }

    }

    /**
     * key与节点进行映射
     */
    HashMap<Integer,node>map=new HashMap<Integer, node>();

    doubleList doubleList=new doubleList();
    /**
     * 以 正整数 作为容量 capacity 初始化 LRU 缓存
     */
    int capacity;
    public LRUCache(int capacity) {
        this.capacity=capacity;
    }

    /**
     * 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
     * 必须以 O(1) 的平均时间复杂度运行。
     */
    public int get(int key) {
        if(map.containsKey(key)){
            int val=map.get(key).val;
            // 利⽤ put ⽅法把该数据提前
            put(key, val);
            return val;
        }
        else
            return -1;
    }

    /**
     *  如果关键字 key 已经存在，则变更其数据值 value ；
     *  如果不存在，则向缓存中插入该组 key-value 。
     *  如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
     *  必须以 O(1) 的平均时间复杂度运行。
     */
    public void put(int key, int value) {
        node node = new node(key, value);
        if (map.containsKey(key)) {   //如果 key 已经存在，先删除原有节点
            doubleList.remove(map.get(key));
        } else if (doubleList.size == capacity) {  //逐出 最久未使用的关键字。
            node last = doubleList.removeLast();
            map.remove(last.key);
        }
        //则变更对应节点和map映射信息
        map.put(key,node);
        doubleList.addFirst(node);
    }
}
